package com.leetcode.背包问题;

/**
 * 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
 *
 * 对于01背包，如果利用一维dp来实现，则在遍历背包容量的时候一定要使用倒叙
 * 因为，如果是正序，那下次需要用到的dp[j -weight[i]]有可能会被更新，则结果就会出错
 * 倒叙不会出错是因为，dp[j]只会被dp[j]左边的数据影响,从右到左遍历更新dp[j]，不会影响到dp[j]左边的数据
 *
 */
public class CanPartition416 {
	public static void main(String[] args) {
		int[] nums = new int[] { 1, 2, 5 };
		boolean can = canPartition(nums);
		System.out.println(can);
	}

	public static boolean canPartition(int[] nums) {
		if (nums.length < 1) {
			return false;
		}
		int sum = 0;
		for (int i = 0; i < nums.length; i++) {
			sum += nums[i];
		}
		// 和为奇数就不可能分为两个相等的子集
		if ((sum & 1) == 1) {
			return false;
		}
		int halfSum = sum / 2;
		// 现在问题变为：有无任意N个数的和为halfSum
		/**
		 * 问题化为01背包：物品的 价值 和 重量 都为元素的数值，背包容量为halfSum
		 * 当背包容量为halfSum时，如果此时装的最大价值为halfSum，则表示有若干个物品的重量也为halfSum
		 */
		// 定义dp数组
		int[] dp = new int[halfSum + 1];
		// 初始化一维dp的'第一行'
		for (int i = 0; i < dp.length; i++) {
			if (i >= nums[0]) {
				dp[i] = nums[0];
			}
		}
		for (int i = 1; i < nums.length; i++) {
			// 用一维dp背包容量一定要倒叙遍历，确保每种物品只放了一次
			for (int j = halfSum; j >= nums[i]; j--) {
				if (j == 0) {
					dp[j] = 0;
				} else if (j - nums[i] >= 0) {
					dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
				}
			}
		}
		if (dp[halfSum] == halfSum) {
			return true;
		}
		return false;
	}
}
